package com.itheima.search;

public class A03_BlockSearchDemo1 {
    public static void main(String[] args) {
        //分块查找
        //分块
        int[] arr = {21, 23, 28, 15,
                11, 1, 5, 8,
                31, 29, 38, 35,
                52, 55};

        //分开存起来
        //创建Block的对象，分成4块
        Block b1 = new Block(28, 15,0, 3);
        Block b2 = new Block(11, 1,4, 7);
        Block b3 = new Block(38, 29,8, 12);
        Block b4 = new Block(55, 52,13, 14);

        //存入数组
        Block[] bArr = {b1, b2, b3, b4};

        //要找的数字
        int num = 5;

        //分好块了，开始查找
        int index = getIndex(bArr, num, arr);
        System.out.println(index);
    }

    private static int getIndex(Block[] bArr, int num, int[] arr) {
        //先找在哪个块
        int index1 = index(bArr, num);

        //先判断是否存在
        if (index1 == -1) {
            System.out.println("不存在");
            return -1;
        }

        //再遍历这个块里面的数据
        for (int i = bArr[index1].getStartIndex(); i <= bArr[index1].getEndIndex(); i++) {
            if (num == arr[i]) {
                //找到了
                return i;
            }
        }
        return -1;
    }

    private static int index(Block[] bArr, int num) {

        //循环Block数组，得到里面最大值，num在其第一次小于某个块最大值的那个块里
        for (int i = 0; i < bArr.length; i++) {
            if (num <= bArr[i].getMax()&&num>=bArr[i].getMin()) {
                //第一次小于，说明就在这个块
                return i;
            }
        }
        return -1;
    }
}

class Block {
    private int max;
    private int min;
    private int startIndex;
    private int endIndex;


    public Block() {
    }

    public Block(int max, int min, int startIndex, int endIndex) {
        this.max = max;
        this.min = min;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    /**
     * 获取
     *
     * @return max
     */
    public int getMax() {
        return max;
    }

    /**
     * 设置
     *
     * @param max
     */
    public void setMax(int max) {
        this.max = max;
    }

    /**
     * 获取
     *
     * @return min
     */
    public int getMin() {
        return min;
    }

    /**
     * 设置
     *
     * @param min
     */
    public void setMin(int min) {
        this.min = min;
    }

    /**
     * 获取
     *
     * @return startIndex
     */
    public int getStartIndex() {
        return startIndex;
    }

    /**
     * 设置
     *
     * @param startIndex
     */
    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    /**
     * 获取
     *
     * @return endIndex
     */
    public int getEndIndex() {
        return endIndex;
    }

    /**
     * 设置
     *
     * @param endIndex
     */
    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    public String toString() {
        return "Block{max = " + max + ", min = " + min + ", startIndex = " + startIndex + ", endIndex = " + endIndex + "}";
    }
}
